\section{Introduction}
\label{sec-introduction}

In a language such as \commonlisp{} \cite{ansi:common:lisp}, it is
hard to avoid redundant tests, even if the programmer goes to great
lengths to avoid such redundancies.  The reason is that even the
lowest-level operators in \commonlisp{} require \emph{type checks} to
determine the exact way to accomplish the operation, so that two or
more calls to similar operators may introduce redundant tests that are
impossible to eliminate manually.

As an example of such an introduction of redundant tests, consider the
basic list operators \texttt{car} and \texttt{cdr}.  We can think of
these operators to be defined%
\footnote{For these particular operators, an implementation may use
  some tricks to avoid some of these tests, but such tricks are not
  generally usable for other operators.  We still prefer to use
  \texttt{car} and \texttt{cdr} as examples, because their definitions
  are easy to understand.}
in a way similar to the code below:

\begin{verbatim}
  (defun car (x)
    (cond ((consp x) (cons-car x))
          ((null x) nil)
          (t (error 'type-error ...))))

  (defun cdr (x)
    (cond ((consp x) (cons-cdr x))
          ((null x) nil)
          (t (error 'type-error ...))))
\end{verbatim}

\noindent
where \texttt{cons-car} and \texttt{cons-cdr} are operations that
assume that the argument is of type \texttt{cons}.  These operations
are implementation defined and not available to the application
programmer.

Now consider some typical%
\footnote{In this case, the programmer might use the standard macro
  \texttt{destructuring-bind}, but for reasons of simplicity, that
  macro will very likely expand to calls to \texttt{car} and
  \texttt{cdr}, rather than to some implementation-specific code that
  avoids the redundant tests.}
use of \texttt{car} and \texttt{cdr} such as
in the following code:

\begin{verbatim}
  (let ((a (car x))
        (b (some-function)
        (c (cdr x)))
    ...)
\end{verbatim}

After the inlining of the \texttt{car} and \texttt{cdr} operations,
the code looks like this:

\begin{verbatim}
  (let ((a (cond ((consp x) (cons-car x))
                 ((null x) nil)
                 (t (error 'type-error ...)))
        (b (some-function)
        (c (cond ((consp x) (cons-cdr x))
                 ((null x) nil)
                 (t (error 'type-error ...)))
    ...)
\end{verbatim}

We notice that the test for \texttt{consp} occurs twice, and that the
second occurrence is \emph{dominated by} the first one, i.e., every
control path leading to the second occurrence must pass by the first
occurrence as well.

As a consequence, the outcome of the second test for \texttt{consp} is
always the exact same as the outcome of the first one.
Unfortunately, this fact can not be easily exploited.  To see why, we
need to study the intermediate code generated by a typical compiler as
a result of compiling the example program.  The result is shown in
\refFig{fig-example-naive}.

\begin{figure}
\begin{center}
\inputfig{fig-example-naive.pdf_t}
\end{center}
\caption{\label{fig-example-naive}
Control flow generated by a typical compiler.}
\end{figure}

As \refFig{fig-example-naive}, shows, the intermediate code takes the
form of a \emph{control-flow graph} in which the nodes are
\emph{instructions} and the arcs represent the control flow.  When we
use the terms \emph{predecessor} and \emph{successor}, they refer to
the relationship between two instructions in the control-flow graph,
as defined by the control arcs.

In \refFig{fig-example-naive}, we have omitted references to data so
as to simplify the presentation.  In this intermediate representation,
we have also eliminated scoping constructs, so that liveness of a
variable is defined to be between its first assignment and its last
use.  Each control arc is annotated by a type descriptor, indicating
the type of the variable \texttt{x} at that point in the execution of
the program.

After the first \texttt{let} binding has been executed, the control
arc with the type \texttt{cons} and that with the type \texttt{null}
both arrive at the instruction that calls \texttt{some-function} which
is the start of the second \texttt{let} binding.  As a consequence,
after the second \texttt{let} binding has been established, the type
information available for \texttt{x} is \texttt{(or cons null)}, which
is the same as \texttt{list}.

In order to avoid the second test for \texttt{consp}, we need to
\emph{replicate} the instructions corresponding to the establishment
of the second \texttt{let} binding.  In this paper, we introduce a
technique for accomplishing this replication using \emph{local graph
  rewriting}.  The advantage of this technique is that it is very
simple to implement, and that its semantic soundness is trivial to
prove.  We also prove that the technique always terminates, no matter
how complicated the intermediate computation between the two tests.
